"""
Implementation of a list with stable index positions.
"""

class ManagedList(list):
    """This is a list where index positions are stable, i.e, whenever an element
    is removed (with del), the array is not shrunk, but rather, the position is
    marked as free. On the other hand, rather than appending, one may insert 
    a new value in order to reuse freed space"""
    
    def __init__(self, *args):
        "Creates a managed list"
        super(ManagedList, self).__init__(*args)
        self.freeslots = []
    
    def __delitem__(self, key):
        "Marks the element as unused (rather than removing it)"
        self.freeslots.append(key)
        self[key] = None
        
    def insert(self, value):
        "Puts the value somewhere in the list. Returns the index used."
        if self.freeslots!=[]:
            index = self.freeslots.pop()
        else:
            index = len(self)
            self.append(None)
        self[index] = value
        return index
        
    def usedindices(self):
        "Generates all occupied indices, i.e., all positions which are not None"
        for i in range(len(self)):
            if self[i] is not None: yield i
            
    def usedvalues(self):
        "Generates all non-null values"
        for i in range(len(self)):
            if self[i] is not None: yield self[i]
        

if __name__=="__main__":
    # A simple test program
    l = ManagedList([100,20,306,9])
    print l
    del l [2]
    del l [0]
    print l
    print map(lambda i: l[i], l.usedindices())
    print map(lambda v: v, l.usedvalues())
    l.insert(25)
    l.insert(30)
    l.insert(35)
    print l

